1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to managing neighbor nodes and setting a routing path. More particularly, the present invention relates to a method and an apparatus for setting a routing path based on a stable network topology formed by using routing information of neighbor nodes having a higher level of link quality in a mobile ad hoc network environment.
2. Description of the Related Art
A mobile ad hoc network (hereinafter referred to as “MANET”) is formed with portable network devices (hereinafter referred to as “nodes”) such as notebooks, PDAs, or other portable network devices known in the art interconnected through wireless links not based on infrastructure.
In a MANET, the network topology changes regularly due to the mobility of nodes forming the network. A method for monitoring the changes in the network topology is to have each node forming the MANET periodically broadcast a control packet including its own routing information. An example of the control packet is a hello packet, which is mainly used in proactive mechanisms which are the routing protocol for MANET.
If the network topology is known based on the routing information of the control packet broadcast from neighbor nodes, each node can set a routing path through which a data packet to be transmitted by the node will pass. An operation to set a routing path will be explained with reference to FIG. 1.
FIG. 1 illustrates a MANET network topology according to the conventional art.
The MANET network topology and operation for setting a routing path in conventional art will be explained based on an example node A. Node A receives control packets from neighbor nodes (nodes B, C, and D) that are within a 1 hop region 130, whereby the node A senses the existence of the neighbor nodes. When the neighbor nodes are sensed, node A registers the neighbor nodes that transmitted the control packets in a neighbor table. Node identifiers to identify neighbor nodes and link information to indicate links with neighbor nodes are registered in the neighbor table. When no control packet is received from a neighbor node registered in the neighbor table for a certain period, the entry of the concerned neighbor node is deleted from the neighbor table.
Node A ascertains the network topology by using routing information of neighbor nodes registered in the neighbor table. As shown in FIG. 1, lines interconnecting nodes imply that the nodes are directly interconnected through a wireless link.
If the network topology is known, node A calculates a routing path, which can be used when transmitting a data packet to a destination node. For example, when node A transmits a data packet to a node F, a first path 110 involving a node B and a node E, or a second path 120 involving a node C may be set.
When the data packet is transmitted through the first path 110, the data packet has to pass through more nodes than when it is transmitted through the second path 120. The greater number of nodes in the first path implies that more network resources are consumed when the first path 110 is used to transmit the data packet than when the second path 120 is used to transmit the same data packet. Thus, according to the MANET network topology operation for setting a routing path in the conventional art, the second path 120 is set as a routing path in order to minimize the traveling path of the data packet.
As described above, in the conventional art, a routing path is set so that a traveling path of the data packet can be minimized to thereby efficiently use limited wireless network resources. However, since the conventional art operation does not consider the link quality of nodes, network resources may be wasted.
Because MANET uses a wireless medium in order to transmit a data packet, the transmission success of the data packet depends upon the link quality at the time of data packet transmission. Because of the inherent properties of the wireless medium, as the transmission range increases, the received signal intensity of the data packet becomes weaker, until the data packet is routed by another node. Thus, it is implicit that the possibility of a transmission error increases as the transmission range of the data packet increases. Especially, since the link quality between a sending node and a node placed at the boundary of the transmission range of the sending node is low, the data packet transmitted to this node is likely to be lost.
As illustrated in FIG. 1, since node C is placed near the boundary 130 of the transmission range of node A, node A and node C are interconnected by a low quality link. Accordingly, the possibility of success of data packet transmission between node A and node C is low. That is, when the second path 120 is set as a routing path (according to the conventional art) so that node A may transmit a data packet to node F, transmission of the data packet may fail because of the low quality of the link between node A and node C. If transmission of the data packet fails, node A tries to re-transmit the data packet. However, unless the link quality between node A and node C is improved, the data packet transmission error may reoccur. Also, the more the data packet is re-transmitted, the more network resources are wasted.
Accordingly, to efficiently use network resources, the first path 110, which is a relatively stable link, is desirably set as the routing path even though traveling distance of the data packet is relatively longer than when the second path 120 is set as the routing path.
When node C, which is at the transmission boundary 130, broadcasts a control packet, the possibility that the control packet is successfully transmitted to node A is also low. Accordingly, the control packet transmitted from the node C may not be received by the node A for a time. As a result, the entry of node C may be frequently deleted from the neighbor table (regarding neighbor nodes of node A) and again registered in the neighbor table.
Therefore, nodes which ascertain the network topology through the neighbor table have unreliable knowledge of the network topology because of the low quality links.
Korean Unexamined Patent Publication No. 10-2004-0013744, entitled “Method, Apparatus and Data Structure for Synchronizing Link States in an Ad hoc Network”, discloses a technique that is capable of quickly synchronizing link states without overhead, wherein each node broadcasts information on the state of a directly linked neighbor node, stores the link state information received from the neighbor node and then broadcasts it again to the neighbor node. Accordingly, the overhead resulting from broadcasting an entire routing table (that each node possesses) in order to ascertain the network topology can be reduced. Despite this technique, problems such as data packet transmission errors and an unstable network topology due to neighbor nodes having low link quality still occurs.
Accordingly, there is a need for a technique to provide a stable network topology and routing path.